Digital imaging includes many different operations such as capture, printing, and transformation. Examples of transformation are changing image size, changing image resolution, colorizing, and half toning. Colorizing an operation converting a gray scale image to a color image. Half toning is an operation converting a gray scale image to a binary image made of black and white pixels.
A digital image is made of pixels. An 800×600 digital image is 800 pixels wide and 600 pixels high. There are many varieties of pixels, including color pixels, gray scale pixels, and black and white pixels. A black and white pixel is either black or white. A gray scale pixel is a shade of gray. The most common gray scale has 256 shades of gray ranging from white to black where each shade is represented by a value, or number, between 0 and 255. A color pixel can take many different forms. One popular form is using 3 values denoting shades of red, green, and blue. Similar to gray scale, there can be 256 shades of red, 256 shades of green, and 256 shades of blue. Those skilled in the arts of digital imaging or printing are familiar with these and many other ways to digitally represent an image.
Every pixel in a digital image has other pixels that are adjacent to or otherwise near it. A 3×3 pixel neighborhood is 3 pixels wide, 3 pixels high, and contains 9 pixels. There is 1 center pixel in the middle of the 3×3 neighborhood and the other 8 pixels are the center pixel's adjacent pixels. Adjacent pixels are separated by a 1 pixel distance. A 5×5 pixel neighborhood has a center pixel and 24 pixels that are at most 2 pixels away from the center pixel.
Statistics are used to describe the distribution of a set of numbers. The numbers can be obtained from any data source, including pixel values in a digital image. Mean, median, spread, maximum, minimum, variance, and population are commonly used statistics. Those skilled in the statistical arts know these and many other statistics as well as methods for calculating the statistics when given a set of numbers.
The maximum of a set of numbers is the largest number in the set. The minimum of a set of numbers is the smallest number in the set. The population of a set of numbers is how many numbers are in the set. The spread of a set of numbers is the maximum minus the minimum. The mean of a set of numbers is the sum of the numbers in the set divided by the population size. The median of a set of numbers is the smallest number in the set that is larger than or equal to half of the numbers in the set. The variance of a set of numbers can be calculated by summing the squares of the numbers in the set, subtracting the population size times the squared mean, and dividing by the population size decremented by one. The symmetry of a set of numbers is a value quantifying how evenly the numbers are distributed about their mean.
A pixel neighborhood has statistics. The value of the pixels in the neighborhood can be treated as any other set of numbers. As such, the pixel neighborhood has a mean, median, variance, spread, maximum, minimum, and population size. For example, a 3×3 pixel neighborhood has a population size of 9. In some calculations the center pixel is not used, giving a population size of 8.
Digital images can be transformed via neighborhood operations. A neighborhood operation is the substitution of a pixel neighborhood's center pixel by a substitution value based on the neighborhood. For example, the value of a neighborhood's center pixel can be substituted by the neighborhood mean. Some transformation algorithms create a new image out of the substitution values and leave the original image unchanged. Other transformation algorithms operate in place by directly changing values in the original image. Those skilled in the art of digital imaging know these and many other ways to implement neighborhood transformations.
Neighborhood operations for transforming a binary image, also called a half toned image, to a gray scale image is discussed in U.S. Pat. No. 6,343,159, titled “Method and apparatus for modeling and reconstruction of halftoned images”.
Smoothing is a neighborhood transformation in which the center value of a pixel neighborhood is selected based on a weighted summation across the pixel neighborhood. Linear interpolation is a neighborhood operation based on linear analysis of the center pixel's neighbors. Those skilled in digital imaging often refer to smoothing as low-pass filtering and know many ways to calculate and use low pass filters as well as many linear interpolation methods.
Frequency interpolation can be used to replace pixels in a large neighborhood or entire image. The frequency content of the image or neighborhood can be obtained and used to calculate values for pixels that are absent or corrupt in the original image.
Mapping is a transformation that uses a map. A map can be represented as a table of input values and output values. Each input value has an associated output value. For example, a very simple map has a single input value of 100 and a substitution value of 125 associated with it. Transforming a set of numbers such as {0, 50, 100, 150, 200} using the map results {0, 50, 125, 150, 200}. The only difference is that the value of 100 is mapped to 125. A larger map can result in more numbers being mapped.
As discussed above, a digital image can be treated as a set of numbers. As such, a map can be used to transform a digital image. Maps are helpful when images have been modified, but the exact modification is unknown. As such, a group of input images is known and a modified image corresponding to each input image is known. The modified images are often called the desired images. The collection of input images and desired images is called a training set. Many algorithms exist that produce maps when given a training set. One problem is incomplete maps where some input pixel values are not in the map because they were not in the training set. Another problem is noisy maps where some input pixel values occur often in the training set, but with inconsistent output pixel values.
A need therefore exists for systems and methods that can transform an input image to an acceptable output image when incomplete or noisy maps are used. Such a goal can be accomplished through the application of code values and analytic substitutions.